public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {4,3,5,1,8,2,7,6,9,10};
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            shellSort(arr, gap);
        }
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }

    private static void shellSort(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - gap;
            for (; j >= 0 ; j -= gap) {
                if (arr[j] > temp) {
                    arr[j + gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + gap] = temp;
        }
    }


    /**
     * 时间复杂度：O(n^1.25 - n^1.5)  -> n^1.3
     * 空间复杂度：O(1)
     * @param arr
     * @param gap
     */
//    private static void shellSort(int[] arr, int gap) {
//        for (int i = gap; i < arr.length; i++) {
//            int temp = arr[i];
//            int j = i - gap;
//            for (; j >= 0; j -= gap) {
//                if (arr[j] > temp) {
//                    arr[j + gap] = arr[j];
//                } else {
//                    break;
//                }
//            }
//            arr[j + gap] = temp;
//        }
//    }


}
